package string;

import org.junit.Test;

/**
 * @Description 剑指 Offer 58 - I. 翻转单词顺序 https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/
 * @Author Firenut
 * @Date 2023-01-27 00:38
 */
public class T58_I_reverseWords {
    @Test
    public void test() {
//        System.out.println(reverseWords1("the sky is blue"));
        System.out.println(reverseWords1("  hello world!  "));
    }

    // 法2: 使用双指针,定位每一个字符串的起始索引和结束索引,然后用StringBuilder来存结果
    public String reverseWords1(String s) {
        int i,j;
        s = s.trim();
        i = j = s.length() - 1;

        StringBuilder ans=new StringBuilder();

        while(i>=0){
            while(i>=0 &&s.charAt(i)!=' '){
                i--;
            }

            ans.append(s.substring(i + 1, j + 1)).append(" ");
            while(i>=0&&s.charAt(i)==' '){
                i--;
            }
            j=i;
        }
        return ans.toString().trim();
    }

    // 法1: 使用正则,按照空格切分成字符串,然后倒叙遍历存储到结果集字符串中
    // 时间复杂度: O(n)
    // 空间复杂度: O(n)
    public String reverseWords(String s) {
        String []str = s.trim().split(" "); // n个连续空格会被切成 n-1个""
        StringBuilder res = new StringBuilder();

        for (int i = str.length - 1; i >= 0; i--) {
            if (!str[i].equals("")) {
                res.append(str[i]).append(" ");
            }
        }
        return res.toString().trim();
    }
}